package _220326;

/**
 * @author ShadowLim
 * @create 2022-03-26-10:53
 */

import java.util.Arrays;
import java.util.Scanner;


public class 乘积最大 {
    /**
     * 先对n个数从小到大排序，越往左负数的绝对值越大，越往右，正数的绝对值越大，
     * 如果k==n的话就全部都选，直接遍历相乘，如果k<n，k是偶数，答案必然是大于0 的数，
     * 每次选出左边两个数相乘，右边两个数相乘，然后比较乘之后的大小。
     * 如果k是奇数，先把最大的数选出，然后k--，把奇数情况转化为偶数情况。
     *
     */
    static int n, k;
    static int[] a;
    static int[] res;
    static int MOD = 1000000009;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        a = new int[n];
        res = new int[k];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

        Arrays.sort(a);
        long res = 1;
        int l = 0, r = n - 1;
        int sign = 1;

        if ((k & 1) == 1) {   // 如果k是奇数，先把奇数转化为偶数
            res = a[r--];
            k--;    // 偶数化奇数
            if (res < 0) {
                sign = -1;
            }
        }

        while (k != 0) {
            // 每次选取前面2个数和后面2个数进行比较
            long x = (long)a[l] * a[l + 1], y = (long)a[r - 1] * a[r]; // 一定要强转 不然只过60%
            if (x * sign > y * sign) {
                res = x % MOD * res % MOD;
                l += 2;
            } else {
                res = y % MOD * res % MOD;
                r -= 2;
            }
            k -= 2;
        }
        System.out.println(res);
    }
}
